11590 - Prefix lookup/11590.9.cpp

   1 /*
   2   Accepted, but the fastest is 11590.7.cpp
   3 */
   4 using namespace std;
   5 #include <algorithm>
   6 #include <iostream>
   7 #include <iterator>
   8 #include <sstream>
   9 #include <fstream>
  10 #include <cassert>
  11 #include <climits>
  12 #include <cstdlib>
  13 #include <cstring>
  14 #include <string>
  15 #include <cstdio>
  16 #include <vector>
  17 #include <cmath>
  18 #include <queue>
  19 #include <deque>
  20 #include <stack>
  21 #include <list>
  22 #include <map>
  23 #include <set>
  24
  25 #define D(x) cout << #x " = " << (x) << endl
  26
  27 typedef unsigned long long Int;
  28 const int BUFSIZE = 256;
  29 char buf[BUFSIZE];
  30
  31 int M;
  32 map<string, Int> ans;
  33
  34 struct node{
  35   node * left, * right;
  36   bool end; //is this node a complete prefix?
  37   node(bool e) : end(e) {
  38     left = right = NULL;
  39   }
  40 };
  41
  42 //not used, because I love to waste memory (makes me feel sexy)
  43 void clean(node * n){
  44   if (n == NULL) return;
  45   clean(n->left); clean(n->right);
  46   delete n;
  47 }
  48
  49 Int f(string s, node * n){ //s = string built so far, n = the node we are standing at
  50   Int left = 0, right = 0, ret = 0;
  51   if (n->left != NULL){
  52     left = f(s + "0", n->left);
  53   }
  54   if (n->right != NULL){
  55     right = f(s + "1", n->right);
  56   }
  57   ret += left + right;
  58
  59   if (n->end){
  60     Int howmany;
  61     if (M - s.size() < 64){ //we are safe from overflow
  62       Int x = ((1ULL) << (M - s.size())); //2^(m - |s|)
  63       howmany = x - left - right;
  64     }else{ //2^64 overflows!
  65       Int x = 0;
  66       x = ~x; // (x = ~0ULL) <-> (x = 2^64 - 1)
  67       howmany = x - left - right + 1;
  68     }
  69     ret += howmany;
  70     ans[s] = howmany;
  71   }
  72   return ret;
  73 }
  74
  75 int main(){
  76   int n;
  77   while (true){
  78     assert(scanf("%d %d ", &n, &M) == 2);
  79     if (n == 0 && M == 0) break;
  80     //D(n); D(M);
  81     ans.clear();
  82     node * root = new node(true);
  83     while (n--){
  84       fgets(buf, BUFSIZE, stdin);
  85       node * cur = root;
  86       for (int i=0; ; ++i){
  87         if (buf[i] == '*'){
  88           cur->end = true;
  89           break;
  90         }
  91         if (buf[i] == '0'){
  92           if (cur->left == NULL) cur->left = new node(false);
  93           cur = cur->left;
  94         }else if (buf[i] == '1'){
  95           if (cur->right == NULL) cur->right = new node(false);
  96           cur = cur->right;
  97         }
  98       }
  99     }
 100
 101     f("", root);
 102
 103     int K;
 104     scanf("%d ", &K);
 105     while (K--){
 106       fgets(buf, BUFSIZE, stdin);
 107       int end = strlen(buf)-1;
 108       while (buf[end] != '*') end--;
 109       buf[end] = 0;
 110       Int t = ans[string(buf)];
 111       assert(t >= 0);
 112       printf("%llu\n", t);
 113     }
 114
 115     scanf(" "); //empty line
 116     puts("");
 117   }
 118   return 0;
 119 }